package com.gitee.feizns.explore.data_structure.linked_list.singly.copy_random_list;

import java.util.HashMap;
import java.util.Map;

/**
 * @author feizns
 * @since 2019/10/10
 */
public class CopyRandomListMain {

    public static void main(String[] args) {
        Node node = create();
        node.print();
        Node node1 = copyRandomList(node);
        node1.print();
        System.out.println(node1.random.val);
    }

    public static Node copyRandomList(Node head) {
        Map<Node, Node> oldAndNewNodes = new HashMap<>();

        for (Node curt = head; curt != null; curt = curt.next) {
            if ( !(oldAndNewNodes.containsKey(curt)) )
                oldAndNewNodes.put(curt, new Node(curt.val));

            if ( curt.random != null && !(oldAndNewNodes.containsKey(curt.random)) )
                oldAndNewNodes.put(curt.random, new Node(curt.random.val));
        }

        if ( head != null ) {
            Node ret = oldAndNewNodes.get(head);
            if ( head.random != null )
                ret.random = oldAndNewNodes.get(head.random);
            for (Node curt = head.next, prev = ret; curt != null; curt = curt.next) {
                prev.next = oldAndNewNodes.get(curt);
                prev = prev.next;
                if ( curt.random != null )
                    prev.random = oldAndNewNodes.get(curt.random);
            }
            return ret;
        }
        return null;
    }

    private static Node create() {
        Node ret = new Node(1);
        ret.next = new Node(2);
        ret.random = ret.next;
        return ret;
    }

}
